Compared with geosynchronous earth orbit (GEO) based satellite communication networks, satellite communication networks at a low earth orbit (LEO) orbit have much smaller propagation delays. And due to much reduced communication distances to earth, LEO communication systems have low power requirements on ground terminals, which may allow broadband communication services to be used on small size mobile terminals. However, a constellation of LEO satellites is needed to provide global coverage due to reduced coverage areas (footprints) of each LEO satellite. Satellites in the LEO constellation are moving with respect to each other and its network users, which may lead to a dynamic network. As a result, highly efficient routing methods are needed for real-time evaluation and for update of routing paths for the delivery of data packages in an IP-based LEO satellite network.
Although topology of the LEO satellite network is time-varying, the topology is known and predictable. This makes the link state based routing approach, where every node constructs a map of network connectivity based on the states of the communication links, more desirable over the distance vector approach, which works by having neighboring nodes share their routing tables. Dijkstra's algorithm is the foundation of most link state based routing protocols and is able to effectively calculate the shortest path between any two nodes in a network of an arbitrary topology. However, as a general shortest path algorithm, Dijkstra's algorithm does not exploit the topology features of a LEO constellation. In addition, complexity of the Dijkstra's algorithm is still too high for the routing needs in IP-based LEO satellite networks.